Nearest neighbor classifier is one of the most popular approaches for classification. It is naturally suitable for tasks involving many classes. For example, there are more than thousands of classes in the case of face recognition and OCR for Chinese characters. The success of nearest neighbor classifier highly depends on the quality of distance metric of data, therefore metric learning has been an important component of machine learning. A learned distance metric can also be transferred to similar tasks. For example, a distance metric can be learned from a group of subjects with many training face images, and use the learned metric to recognize a different group of subjects with only one face image per subject. One major issue of metric learning is its prohibitive computation costs, because the training algorithms typically operate with pairs or triples of training examples.
Many approaches exist for distance metric learning. Unsupervised approaches, such as PCA family, have been widely used. For example, Eigenface has been used for face recognition and gender recognition. In the cases where additional label information is available, supervised approaches may generally lead to higher-quality distance metrics. Among supervised approaches, linear discriminant analysis, such as Fisherface, is widely used because of simplicity and relatively high quality. Machine learning practitioners usually pursue approaches resulting into higher quality metrics, as the cost of computation is decreasing.
To learn metric for nearest neighbor classifiers in many-class problems, we prefer nearest-neighbor-based approaches, because the triple constraints are weaker than pairwise constraints, and directly related to the decision rule of nearest-neighbor classification—in order to correctly classify, essentially we need to ensure the triple-wise relationship that the distance between data and from the same class is smaller than that between and from different classes, while caring less about the absolute values of pair-wise distances. Thereafter in this paper, we will call the triple-wise approach by nearest-neighbor-based metric learning.